﻿#include <iostream>
#include <algorithm>
using namespace std;

const int n = 5;
int c = 10;
int w[n] = { 2, 2, 6, 5, 4 };
int v[n] = { 6, 3, 5, 4, 6 };

int knapSack(int x[]) {
	int i, j;
	int * *V = new int* [n + 1];
	for (i = 0; i <= n; i++) {
		V[i] = new int[c + 1];
	}

	for (i = 0; i <= n; i++) {					//初始化数组
		for (j = 0; j <= c; j++) {
			V[i][j] = 0;
		}
	}

	for(i = 1; i <= n; i++) {					//计算第i行，进行第i次迭代
		for(j = 1; j <= c; j++) {
			if(j < w[i - 1]) {
				V[i][j] = V[i - 1][j];
			} else {
				V[i][j] = max(V[i - 1][j], V[i - 1][j - w[i - 1]] + v[i - 1]);
			}
		}
	}
	for(j = c, i = n; i > 0; i--) {				//求装入背包的物品
		if(V[i][j] > V[i - 1][j]) {
			x[i - 1] = 1;
			j = j - w[i - 1];
		} else {
			x[i - 1] = 0;
		}

	}

	int a = V[n][c];
	for (i = 0; i <= n; i++) {
		delete[] V[i];
	}

	return a;										//返回背包取得的最大价值
}

int main() {
	int x[n] = {0};
	cout << knapSack(x) << endl;

	system("pause");
	return 0;
}